package org.datacoder.geocoding.datastructures.rectangles

import org.datacoder.geocoding.*
import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.Jurisdiction

class LayeredSubIntervalTree {

    public LayeredSubIntervalTreeNode root

    public LayeredSubIntervalTree(List<GeoRectangle> geoRectangles){
        root = createNode(geoRectangles)
    }

    public LayeredSubIntervalTreeNode createNode(List<GeoRectangle> geoRectangles){
        if(geoRectangles.isEmpty()){
            return null
        }

        LayeredSubIntervalTreeNode lsitNode = new LayeredSubIntervalTreeNode()
        double min
        double max = -1000

        Collections.sort(geoRectangles, new GeoRectangleStartPointComparator(GeoShape.LAT))
        min = geoRectangles.get(0).lat1
        for(gr in geoRectangles){
            if(max < gr.lat1){
                max = gr.lat1
            }
        }

        int numGeoRectangles = geoRectangles.size()
        lsitNode.center = geoRectangles.get((Integer)(numGeoRectangles/2)).retrieveCenter(GeoShape.LAT)

        List<GeoRectangle> leftGeoRectangles = new ArrayList<GeoRectangle>()
        List<GeoRectangle> rightGeoRectangles = new ArrayList<GeoRectangle>()

        int i
        for(i = 0; i < numGeoRectangles; i++){
            GeoRectangle gr = geoRectangles.get(i)
            if(gr.lat1 > lsitNode.center){
                break
            }
            if(gr.lat2 > lsitNode.center){
                lsitNode.addGeoRectangle(gr)
            }else{
                leftGeoRectangles.add(gr)
            }
        }
        for(; i < numGeoRectangles; i++){
            rightGeoRectangles.add(geoRectangles.get(i))
        }
        lsitNode.left = createNode(leftGeoRectangles)
        lsitNode.right = createNode(rightGeoRectangles)
        return lsitNode
    }

    public Set<Jurisdiction> findRectanglesContainingPoint(GeoPoint gp){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        LayeredSubIntervalTreeNode lsitNode = root
        while(lsitNode != null){
            if(gp.lat == lsitNode.center){
                for(gr in lsitNode.geoRectanglesByStart){
                    if(gr.containsGeoPoint(gp)){
                        jurisdictions.add(gr.juris)
                    }
                }
                break
            }else if(gp.lat < lsitNode.center){
                for(gr in lsitNode.geoRectanglesByStart){
                    if(gr.lat1 > gp.lat){
                        break
                    }
                    if(gr.containsGeoPoint(gp)){
                        jurisdictions.add(gr.juris)
                    }
                }
                lsitNode = lsitNode.left
            }else{
                for(gr in lsitNode.geoRectanglesByEnd){
                    if(gr.lat2 < gp.lat){
                        break
                    }
                    if(gr.containsGeoPoint(gp)){
                        jurisdictions.add(gr.juris)
                    }
                }
                lsitNode = lsitNode.right
            }
        }
        return jurisdictions
    }
}

